package violentRecursion;

import org.junit.Test;

/*
 *@description 环形子数组的最大和
 *@author hkfan
 *@version 1.0
 *@create 2025/6/23 16:50
 */
public class LeetCode_918 {
    @Test
    public void test(){
        System.out.println(maxSubarraySumCircular(new int[]{-3,-2,-3}));
    }

    /**
     * @description 动态规划，对结果取反，转换为子数组的最小和进而处理两端情况
     * @author hkfan
     * @time 2025/6/30 15:11
     */
    public int maxSubarraySumCircular(int[] nums) {
        //中间部分
        int[] dp = new int[nums.length+1];
        int sum=0;
        for (int i = 1; i < nums.length+1; i++) {
            dp[i]=Math.max(nums[i-1],nums[i-1]+dp[i-1]);
            sum+=nums[i-1];
        }
        int res=dp[1];
        for (int i = 1; i < dp.length; i++) {
            res=Math.max(dp[i],res);
        }
        //包含头部和尾部--问题转换，求最小字串和
        for (int i = 1; i < nums.length+1; i++) {
            dp[i]=Math.min(nums[i-1],nums[i-1]+dp[i-1]);
        }
        for (int i = 1; i < dp.length; i++) {
            if (sum!=dp[i]){
                res=Math.max(sum-dp[i],res);
            }
        }
        return res;
    }


}
